/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-10-30
 * Time: 19:36
 */
public class Solution {


    // DP
    // 每个位置可以通过跳 1、2、3... 步到达
    public int jumpStep1(int number) {
        int[] dp = new int[number+1];
        dp[0] = 1;
        for (int i = 1; i <= number; i++) {
            for (int j = i-1; j >= 0; j--) {
                dp[i] += dp[j];
            }
        }
        return dp[number];
    }


    // 前缀和
    // 由上面的代码觉得每次都循环加上前面的值，这种方法类似于前缀和
    // 但是仔细想一下他又不是前缀和，而是 每次都是前一个值的 2 倍
    public int jumpStep2(int number) {
        int[] dp = new int[number+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i <= number; i++) {
            dp[i] = 2 * dp[i-1];
        }
        return dp[number];
    }


    // 再由上面代码就可以看出其实是 2 的 n-1 次方， 所以直接进行移位即可
    public int jumpStep3(int number) {
        return 1 << (number-1);
    }
}
